﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Spk.Controls.Common;

namespace Spk.Controls.Trees
{
    internal enum NodeVisualRelationship
    {
        Earlier,
        Equal,
        Later
    }

    /// <summary>
    /// Class contains routines regarding operations on the tree
    /// structure (eg. excluding the control states, events etc.)
    /// </summary>
    internal static class TreeStructure
    {
        /// <summary>
        /// Evaluates node's path, eg. indexes of elements
        /// being node's ancestors starting from the root.
        /// </summary>
        private static uint[] GetNodePath(VirtualNode node)
        {
            node.CheckNull("node");

            uint level = TreeStructure.GetNodeLevel(node);
            uint[] result = new uint[level];

            int index = result.Length - 1;

            while (node.Parent != null)
            {
                result[index] = node.Index;
                node = node.Parent;
                index--;
            }

            return result;
        }

        /// <summary>
        /// Adds new child to node
        /// </summary>
        public static VirtualNode AppendChild(VirtualNode node)
        {
            VirtualNode child = new VirtualNode()
            {
                OwnerTree = node.OwnerTree,
                Parent = node,
                PreviousSibling = node.LastChild,
                NextSibling = null,
                Index = node.ChildCount
            };

            // Inserting the newNode to the end of
            // node's child list

            if (node.FirstChild == null)
                node.FirstChild = child;
            if (node.LastChild != null)
                node.LastChild.NextSibling = child;
            node.LastChild = child;
            node.ChildCount++;

            return child;
        }

        public static VirtualNode InsertChildBefore(VirtualNode node)
        {
            if (node.IsRoot)
                throw new InvalidOperationException("Cannot insert node before hidden root node!");

            var parent = node.Parent;

            VirtualNode child = new VirtualNode()
            {
                OwnerTree = node.OwnerTree,
                Parent = node.Parent,
                PreviousSibling = node.PreviousSibling,
                NextSibling = node,
                Index = node.Index,
                Height = 0
            };

            if (parent.FirstChild == node)
                parent.FirstChild = child;

            if (node.PreviousSibling != null)
                node.PreviousSibling.NextSibling = child;
            node.PreviousSibling = child;

            Reindex(node, child.Index + 1);

            parent.ChildCount++;

            return child;
        }

        public static VirtualNode InsertChildAfter(VirtualNode node)
        {
            if (node.IsRoot)
                throw new InvalidOperationException("Cannot insert node after hidden root node!");

            var parent = node.Parent;

            VirtualNode child = new VirtualNode()
            {
                OwnerTree = node.OwnerTree,
                Parent = node.Parent,
                PreviousSibling = node,
                NextSibling = node.NextSibling,
                Index = node.Index + 1,
                Height = 0
            };

            if (parent.LastChild == node)
                parent.LastChild = child;

            if (node.NextSibling != null)
                node.NextSibling.PreviousSibling = child;
            node.NextSibling = child;

            Reindex(child, node.Index + 1);

            parent.ChildCount++;

            return child;
        }

        /// <summary>
        /// Collapses the node
        /// </summary>
        public static void CollapseNode(VirtualNode node)
        {
            node.CheckNull("node");

            if (node.IsRoot)
                throw new InvalidOperationException("Cannot collapse hidden root node!");

            node.IsExpanded = false;
            SetTotalNodeHeight(node, node.Height, false);
        }

        /// <summary>
        /// Checks, which of the two nodes is displayed earlier in the tree
        /// </summary>
        /// <remarks>The method is slow and should not be called in a loop</remarks>
        public static NodeVisualRelationship Compare(VirtualNode node1, VirtualNode node2)
        {
            var history1 = GetNodePath(node1);
            var history2 = GetNodePath(node2);

            int index1 = 0;
            int index2 = 0;

            while (index1 < history1.Length && index2 < history2.Length)
            {
                if (history1[index1] < history2[index2])
                    return NodeVisualRelationship.Earlier;
                else if (history1[index1] > history2[index2])
                    return NodeVisualRelationship.Later;

                index1++;
                index2++;
            }

            if (index1 >= history1.Length && index2 < history2.Length)
                return NodeVisualRelationship.Earlier;
            else if (index1 < history1.Length && index2 >= history2.Length)
                return NodeVisualRelationship.Later;
            else
                return NodeVisualRelationship.Equal;
        }

        /// <summary>
        /// Deletes node
        /// </summary>
        public static void DeleteNode(VirtualNode node)
        {
            if (node.IsSelected || node.IsFocused || node.IsShiftSelectionOrigin)
                throw new InvalidOperationException("Internal error: attempting to delete node with set state flags (selected, focused or shift selection origin)");

            // Remove all children
            DeleteNodeChildren(node);

            // Since it is not root, it always has parent
            var parent = node.Parent;

            // Keeping contracts with siblings and parent
            if (node.PreviousSibling != null)
                node.PreviousSibling.NextSibling = node.NextSibling;
            if (node.NextSibling != null)
                node.NextSibling.PreviousSibling = node.PreviousSibling;
            if (node == parent.FirstChild)
                parent.FirstChild = node.NextSibling;
            if (node == parent.LastChild)
                parent.LastChild = node.PreviousSibling;

            // Reindexing if needed
            if (node.NextSibling != null)
                Reindex(node.NextSibling, node.Index);

            parent.ChildCount--;

            // Reflecting to change in height
            if (parent.IsExpanded)
                SetTotalNodeHeight(parent, -node.TotalHeight, true);

            // Evaluating states of node's parent
            if (parent.ChildCount == 0)
            {
                parent.HasChildren = false;
                if (!parent.IsRoot)
                    parent.IsExpanded = false;
            }

            // Detach node
            DetachNode(node);
        }

        /// <summary>
        /// Removes all node's children
        /// </summary>
        /// <param name="node"></param>
        public static void DeleteNodeChildren(VirtualNode node)
        {
            // TODO: Can be optimized

            var child = node.LastChild;
            while (child != null)
            {
                var prev = child.PreviousSibling;
                DeleteNode(child);
                child = prev;
            }
        }

        /// <summary>
        /// Removes reference to owner tree and neighbor nodes
        /// making node further unusable.
        /// </summary>
        public static void DetachNode(VirtualNode node)
        {
            node.CheckNull("node");

            var child = node.FirstChild;

            // Breaking all connections
            node.OwnerTree = null;
            node.Parent = null;
            node.NextSibling = null;
            node.PreviousSibling = null;
            node.FirstChild = null;
            node.LastChild = null;

            while (child != null)
            {
                var next = child.NextSibling;
                DetachNode(child);
                child = next;
            }
        }
        
        /// <summary>
        /// Evaluates total height of the node (eg. node and
        /// recursively all of its children)
        /// </summary>
        public static uint EvalTotalHeight(VirtualNode node)
        {
            node.CheckNull("node");

            uint totalHeight = node.Height;

            if (node.IsExpanded)
            {
                var childNode = node.LastChild;
                while (childNode != null && IsVisible(childNode))
                {
                    totalHeight += childNode.TotalHeight;

                    childNode = childNode.PreviousSibling;
                }
            }

            return totalHeight;
        }

        /// <summary>
        /// Hides node
        /// </summary>
        public static void HideNode(VirtualNode node)
        {
            if ((node.Parent.IsExpanded))
            {
                uint totalHeight = node.TotalHeight;

                SetTotalNodeHeight(node.Parent, -((int)totalHeight), true);
            }

            node.IsVisible = false;
        }

        /// <summary>
        /// Verifies, whether given node is another node's ancestor
        /// </summary>
        /// <param name="ancestor">Suspected ancestor</param>
        /// <param name="node">Tested node</param>
        /// <param name="acceptEqual">Accept the node itself as its ancestor</param>
        public static bool IsAncestorOf(VirtualNode ancestor, VirtualNode node, bool acceptEqual = false)
        {
            ancestor.CheckNull("ancestor");
            node.CheckNull("node");

            VirtualNode run;
            if (acceptEqual)
                run = node;
            else
                run = node.Parent;

            while (run != null)
            {
                if (run == ancestor)
                    return true;
                run = run.Parent;
            }

            return false;
        }

        /// <summary>
        /// Checks, if node is visible and all its ancestors are visible and expanded
        /// </summary>
        public static bool IsNodeFullyVisible(VirtualNode node)
        {
            node.CheckNull("node");

            bool result = (node.IsVisible);
            if (result && !node.IsRoot)
                result = IsNodeVisiblePath(node);

            return result;
        }

        /// <summary>
        /// Checks, if node is on the visible path, eg. if
        /// all its ancestors are visible and expanded
        /// </summary>
        public static bool IsNodeVisiblePath(VirtualNode node)
        {
            node.CheckNull("node");

            while (!node.IsRoot)
            {
                node = node.Parent;
                if (!node.IsVisible || !node.IsExpanded)
                    return false;
            }

            return true;
        }

        /// <summary>
        /// Checks, whether node is visible
        /// </summary>
        public static bool IsVisible(VirtualNode node)
        {
            node.CheckNull("node");

            return (node.IsVisible);
        }

        /// <summary>
        /// Returns first visible node
        /// </summary>
        /// <param name="root">Tree's root node</param>
        /// <param name="node">Root node of the checked subtree.
        /// This node is excluded from the search.</param>
        /// <returns></returns>
        public static VirtualNode GetFirstVisible(VirtualNode root, VirtualNode node = null)
        {
            if (node == null)
                node = root;

            var result = node;

            if (result.FirstChild != null)
            {
                result = result.FirstChild;

                while (result != null && !IsNodeFullyVisible(result))
                    result = result.NextSibling;

                return result;
            }
            else
                return null;
        }

        /// <summary>
        /// Returns first visible child of a node
        /// </summary>
        public static VirtualNode GetFirstVisibleChild(VirtualNode node)
        {
            node.CheckNull("node");

            VirtualNode result = node.FirstChild;

            while (result != null && !result.IsVisible)
                result = result.NextSibling;

            return result;
        }

        /// <summary>
        /// Returns last node of a subtree (that is recursively last
        /// child of last child of ...)
        /// </summary>
        public static VirtualNode GetLast(VirtualNode root, VirtualNode node = null)
        {
            if (node == null)
                node = root;

            VirtualNode result = node.LastChild;
            while (result != null && result.LastChild != null)
                result = result.LastChild;

            return result;
        }

        /// <summary>
        /// Returns last visible node
        /// </summary>
        public static VirtualNode GetLastVisible(VirtualNode root, VirtualNode node = null)
        {
            root.CheckNull("root");
            if (node == null)
                node = root;

            VirtualNode result = GetLast(root, node);
            while (result != null && result != node && !IsNodeFullyVisible(result))
                result = GetPrevious(result);

            // If there is no visible node
            if (result == node)
                result = null;

            return result;
        }

        /// <summary>
        /// Generates structure describing, which lines shall be drawn
        /// for given tree node.
        /// </summary>
        public static TreeLineKinds[] GetLinesFor(VirtualNode node, bool includeRoot)
        {
            node.CheckNull("node");

            int level = (int)TreeStructure.GetNodeLevel(node);

            if (includeRoot)
                level -= 1;
            else
                level -= 2;

            if (level < 0)
                return new TreeLineKinds[0];

            TreeLineKinds[] result = new TreeLineKinds[level + 1];

            // Line for node
            if (node.Parent.IsRoot)
            {
                bool isFirst = (node == node.Parent.FirstChild || TreeStructure.GetPreviousVisibleSibling(node) == null);
                bool isLast = (node == node.Parent.LastChild || TreeStructure.GetNextVisibleSibling(node) == null);

                if (isFirst && isLast)
                    result[level] = TreeLineKinds.OnlyRoot;
                else if (isFirst)
                    result[level] = TreeLineKinds.FirstRoot;
                else if (isLast)
                    result[level] = TreeLineKinds.Last;
                else
                    result[level] = TreeLineKinds.Middle;
            }
            else
            {
                bool isFirst = (node == node.Parent.FirstChild || TreeStructure.GetPreviousVisibleSibling(node) == null);
                bool isLast = (node == node.Parent.LastChild || TreeStructure.GetNextVisibleSibling(node) == null);

                if (isFirst && isLast)
                    result[level] = TreeLineKinds.OnlyInner;
                else if (isFirst)
                    result[level] = TreeLineKinds.FirstInner;
                else if (isLast)
                    result[level] = TreeLineKinds.Last;
                else
                    result[level] = TreeLineKinds.Middle;
            }

            level--;
            node = node.Parent;

            // Lines for previous levels
            while (level >= 0)
            {
                if (node == node.Parent.LastChild || TreeStructure.GetNextVisibleSibling(node) == null)
                    result[level] = TreeLineKinds.None;
                else
                    result[level] = TreeLineKinds.Line;

                level--;
                node = node.Parent;
            }

            return result;
        }

        /// <summary>
        /// Returns next visible node
        /// </summary>
        /// <param name="node">The start point of search</param>
        /// <param name="fromSibling">Starts the search at start
        /// node's sibling, not child</param>
        /// <returns></returns>
        public static VirtualNode GetNextVisible(VirtualNode node, bool fromSibling = false)
        {
            node.CheckNull("node");

            if (node.IsRoot)
                throw new InvalidOperationException("Cannot evaluate next visible for hidden root node!");

            // If node is not fully visible, seek for first visible parent
            // on the path to root
            VirtualNode result = node;
            if (!IsNodeFullyVisible(node))
                result = GetVisibleParent(result);

            bool done;
            if (!fromSibling && (node.IsExpanded) && result.FirstChild != null)
            {
                result = result.FirstChild;
                done = (result.IsVisible);
            }
            else
                done = false;

            while (!done)
            {
                if (result.NextSibling != null)
                {
                    result = result.NextSibling;
                    done = (result.IsVisible);
                }
                else
                {
                    if (!result.Parent.IsRoot)
                        result = result.Parent;
                    else
                    {
                        result = null;
                        done = true;
                    }
                }
            }

            return result;
        }

        /// <summary>
        /// Returns previous node
        /// </summary>
        public static VirtualNode GetPrevious(VirtualNode node)
        {
            node.CheckNull("node");

            if (node.IsRoot)
                throw new InvalidOperationException("Cannot evaluate previous node for hidden root node!");

            VirtualNode result;

            if (node.PreviousSibling != null)
            {
                VirtualNode last = GetLast(node.PreviousSibling);
                if (last != null)
                    result = last;
                else
                    result = node.PreviousSibling;
            }
            else
            {
                if (node.Parent != null)
                    result = node.Parent;
                else
                    result = null;
            }

            return result;
        }

        /// <summary>
        /// Returns previous visible node
        /// </summary>
        public static VirtualNode GetPreviousVisible(VirtualNode node)
        {
            node.CheckNull("node");

            if (node.IsRoot)
                throw new InvalidOperationException("Cannot evaluate previous visible node for hidden root node!");

            VirtualNode result = node;
            do
            {
                if (!IsNodeFullyVisible(result))
                {
                    result = GetVisibleParent(result);
                    if (result.IsRoot)
                        result = null;
                    VirtualNode marker = GetLastVisible(node);
                    if (marker != null)
                        result = marker;
                }
                else
                {
                    bool done = false;
                    while (!done)
                    {
                        if (result.PreviousSibling != null)
                        {
                            result = result.PreviousSibling;
                            if (result.IsVisible)
                            {
                                VirtualNode marker = GetLastVisible(result);
                                if (marker != null)
                                    result = marker;
                                done = true;
                            }
                        }
                        else
                        {
                            // If no previous siblings are present, the 
                            // parent node is the nearest previous node.
                            result = result.Parent;
                            if (result.IsRoot)
                                result = null;
                            done = true;
                        }
                        
                    }
                }
            }
            while(result != null && (!result.IsVisible));

            return result;
        }

        /// <summary>
        /// Returns next visible sibling of node
        /// </summary>
        public static VirtualNode GetNextVisibleSibling(VirtualNode node)
        {
            node.CheckNull("node");

            do
            {
                node = node.NextSibling;
            }
            while (node != null && !node.IsVisible);

            return node;
        }

        /// <summary>
        /// Returns previous visible sibling of a node
        /// </summary>
        public static VirtualNode GetPreviousVisibleSibling(VirtualNode node)
        {
            node.CheckNull("node");

            do
            {
                node = node.PreviousSibling;
            }
            while (node != null && !node.IsVisible);

            return node;
        }

        /// <summary>
        /// Returns last visible parent on the node's path
        /// </summary>
        public static VirtualNode GetVisibleParent(VirtualNode node)
        {
            node.CheckNull("node");

            var result = node;

            while (!node.IsRoot)
            {
                if (!node.Parent.IsRoot && !IsNodeFullyVisible(result))
                    result = node.Parent;

                node = node.Parent;
            }

            return result;
        }

        /// <summary>
        /// Returns nesting level of node. Returns 0 for root node.
        /// </summary>
        public static uint GetNodeLevel(VirtualNode node)
        {
            node.CheckNull("node");

            uint result = 0;
            while (node.Parent != null)
            {
                result++;
                node = node.Parent;
            }

            return result;
        }

        /// <summary>
        /// Reindexes a set of nodes.
        /// </summary>
        /// <param name="node">The first node to be reindexed</param>
        /// <param name="newIndex">New index for node</param>
        public static void Reindex(VirtualNode node, uint newIndex)
        {
            node.CheckNull("node");
            
            while (node != null)
            {
                node.Index = newIndex;

                newIndex++;
                node = node.NextSibling;
            }
        }

        /// <summary>
        /// Sets height of node.
        /// </summary>
        /// <param name="node">Node, which height is to be changed.</param>
        /// <param name="newHeight">New height of node</param>
        /// <returns>True, if any visible node has been changed. False otherwise.</returns>
        public static bool SetNodeHeight(VirtualNode node, uint newHeight)
        {
            node.CheckNull("node");

            var oldHeight = node.Height;
            node.Height = newHeight;

            var diff = node.Height - oldHeight;

            if (diff > 0)
                return SetTotalNodeHeight(node, diff, true);
            else
                return false;
        }

        /// <summary>
        /// Sets node's total height (that is, height of node and all its children)
        /// </summary>
        /// <param name="node">Node, which total height is to be changed</param>
        /// <param name="newHeight">New value of total height</param>
        /// <param name="relative">Defines, if passed value is a relative change or a new height value.</param>
        /// <returns>True, if any visible node has been changed. False otherwise.</returns>
        public static bool SetTotalNodeHeight(VirtualNode node, long newHeight, bool relative = false)
        {
            long change;
            if (relative)
                change = newHeight;
            else
                change = newHeight - node.TotalHeight;

            if (change == 0)
                return false;

            bool visibleNodeChanged = false;

            bool @continue;
            do
            {
                if (TreeStructure.IsNodeFullyVisible(node))
                    visibleNodeChanged = true;

                node.TotalHeight = (uint)(node.TotalHeight + change);

                @continue = (node.IsVisible 
                    && !node.IsRoot
                    && node.Parent != null 
                    && node.Parent.IsExpanded);

                if (@continue)
                    node = node.Parent;
            }
            while (@continue);

            return visibleNodeChanged;
        }

        /// <summary>
        /// Shows node
        /// </summary>
        public static void ShowNode(VirtualNode node)
        {
            if ((node.Parent.IsExpanded))
            {
                uint totalHeight = node.TotalHeight;

                SetTotalNodeHeight(node.Parent, (int)totalHeight, true);
            }

            node.IsVisible = true;
        }
    }
}
